面试题一道。序列化与反序列化二叉树

牛客网真题链接

定义：

  1. 序列化： 将数据结构或对象转换成二进制串的过程。
  2. 反序列化：将在序列化过程中所生成的二进制串转换成数据结构或者对象的过程。

思路：

  1. 序列化：将二叉树转化成一个字符串，每个节点用分隔符分开。由于二叉树的结构可以由其先序遍历和中序遍历结果来决定。一开始想到用二者的结合，后来觉得太麻烦了。不如直接就用一个，只要把整棵树用特殊字符将空值填充称完全二叉树就行了。有了这个思想，其实不管什么遍历，都可以实现序列化。

  2. 反序列化：模拟遍历。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package interview.leetcode;
/**
 * Created by 44931 on 2017/9/1.
 */
public class Solution2 {
    int index = -1;
    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    String Serialize(TreeNode root, StringBuffer stringBuffer) {
        if (null == root) {
            return String.valueOf(stringBuffer.append("#,"));
        }
        stringBuffer.append(String.valueOf(root.val)+",");
        Serialize(root.left, stringBuffer);
        Serialize(root.right, stringBuffer);
        return String.valueOf(stringBuffer);
    }
    String Serialize(TreeNode root) {
        StringBuffer stringBuffer = new StringBuffer();
        return Serialize(root, stringBuffer);
    }
    TreeNode Deserialize(String str) {
        index++;
        int len = str.length();
        if(index >= len){
            return null;
        }
        String[] strr = str.split(",");
        TreeNode node = null;
        if(!strr[index].equals("#")){
            node = new TreeNode(Integer.valueOf(strr[index]));
            node.left = Deserialize(str);
            node.right = Deserialize(str);
        }
            return node;
    }
    TreeNode Deserialize(String[] temp) {
        index++;
        if (temp.length < 1 || index < 0 || temp.length < index || temp[index].equals("#")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(temp[index]));
        root.left = Deserialize(temp);
        root.right = Deserialize(temp);
        return root;
    }
    public static void frontSearch(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.println(node.val);
        frontSearch(node.left);
        frontSearch(node.right);
    }
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        TreeNode n7 = new TreeNode(7);
        TreeNode n8 = new TreeNode(8);
        TreeNode n9 = new TreeNode(9);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.left = n6;
        n3.right = n7;
        n4.left = n8;
        n4.right = n9;
        System.out.println(solution2.Serialize(n1));
        frontSearch(solution2.Deserialize(solution2.Serialize(n1)));
    }
}